package com.buddy.summary.code.algorithm;

import java.util.Arrays;

public class Heap {

    private static void buildHeap(int[] arr){
        //从最后一个非叶子节点开始,依次做下沉调整
        for (int i=(arr.length-2)/2;i>=0;i--){
            downAdjust(arr,i,arr.length);
        }
    }

    private static void downAdjust(int[] arr, int parentIndex, int length) {
        //temp保存父节点的值
        int temp = arr[parentIndex];
        //找到left child节点
        int childIndex = 2 * parentIndex +1;
        while (childIndex < length){
            //1.找到最小的child:
            //如果有right child 且right child的值小于left child的值,定位到right child
            if (childIndex +1 < length && arr[childIndex +1] < arr[childIndex]){
                childIndex ++;
            }
            //2.比较parent和最小的child的值:
            // 如果parent 的值小于最小的child,不做处理
            if (temp <= arr[childIndex])
                break;
            //否则,将parent赋值最小的child的值(不是真正的交换,只是单向的赋值)
            arr[parentIndex] = arr[childIndex];
            //原来的parent的index变成了最小的child的index
            parentIndex = childIndex;
            //找到最小的child的left child节点
            childIndex = 2 * childIndex +1;
        }
        //将最初的父节点赋值给最小的child
        arr[parentIndex] = temp;
    }

    private static void upAdjust(int[] arr){
        int childIndex = arr.length -1;//找到最后一个插入的叶子节点
        int parentIndex = (childIndex -1)/2;//找到它的父节点
        int temp = arr[childIndex];//temp保存插入的叶子节点
        while (childIndex > 0 && temp < arr[parentIndex]){
            arr[childIndex] = arr[parentIndex];
            childIndex = parentIndex;
            parentIndex = (childIndex -1)/2;
        }
        arr[childIndex] = temp;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{7,1,3,10,5,2,8,9,6};
        buildHeap(arr);
        System.out.println(Arrays.toString(arr));
        arr = new int[]{1,3,2,6,5,7,8,9,10,0};
        upAdjust(arr);
        System.out.println(Arrays.toString(arr));
    }
}
